AUTOMATING THE INCOMPLETE AND CONTRADICTORY INFORMATION PROCESSING

UNCERTAINTY PROCESSING FOR MONITORING LARGE-SCALED DISTRIBUTED SYSTEMS

Igor V. Kotenko

Department of Telecommunication Systems, Signal University, St.-Petersburg

Аннотация — В докладе рассматривается задача обработки неполной и противоречивой информации в сис темах поддержки принятия решений на примере мониторинга состояния глобальных вычислительных сетей. Выделяются различные аспекты оперирования неопределенностью. Модель мира описывается посредством атрибутных грамматик. Представление неполной и противоречивой информации и комбинирование свидетельствами выполняется на основе использования многозначных логик, факторов определенности и комбинированных методов. Задаются базирующиеся на этих методах алгоритмы и проводится их сравнительная оценка.

1. Introduction

The management of incompletence and contradiction in the information systems is an area of increasing interest. To date it is human to perform problem solving and decision making in the environments where received information is pa rtial, approximate, fuzzy or (and) inconsistent. The one of the main issues for the next generation decision support systems is to provide the intelligent processing of such information. At present the various models in the area of intelligent uncertaint y information processing have been developed (certainty factors, bayesian inference, Dempster-Shafer belief function, fuzzy theory, possibility theory, etc.). Each of them has different computational efficiency and expressive adequacy [1]. In order to re present the uncertain information processing in the practical applications a formalism for specifying (1) the world model, (2) a mechanism for reasoning with uncertainty, (3) algorithms (as a kind of knowledge) for making decisions in the selected world model and (4) the tools for selecting from among these algorithms are needed. In this paper we propose the state monitoring techniques for handling incomplete and contradictory information about large-scaled distributed systems (on the example of communi cation networks).

2. Problem Definition

Local and global area communication networks (CN) are considered as the complex systems which are divided into the user systems and data communication subsystems [2]. The latter include switching centers, data communication channel s which employ the primary communication network means. There are a lot of monitoring tasks to control CN. One of the most complex and important task is CN diagnostics (CND) consisted of the CN state checking and the violation reasons detection. A CN aut omation control are provided by special administrative systems including distributed Signal Control Centers.

To fulfill CND it is necessary to collect and process the CN elements (CNE) state data including the critical changes revealance, the violated section and reasons of proper function divergence analysis when CN state checking. The diffi culty of solving this problem firstly is conditioned by the complexity of CN as checked objects because of the CNE territorial distribution, wide nomenclature of the communication means and datamation the CNE are realized by, state changes dynamics, vari ety of structural and functional CNE relations, etc.

Besides of this the state checking points rarefaction (e.g., because of the difficulty or impossibility of checking the analog CN elements without their transition to the unworking state), the several information sources and passes pre sence, hardware and software faults and refusals possibility, data transfer delays, the possibility of using the manual state information input causes the receipt of the incomplete and contradictory information (ICI) by the control objects.

The appearance of such information will not be dangerous when to foresee the ICI revelation capabilities and to design the special real-time ICI handling means. The technique of these means initialization may be as follows. After input data to the administrative system objects the integrity check procedures are executed. If the violations are revealed the degree of the data incompletence and contradiction is evaluated. In accordance with the received value the handling means which imp ly algorithms with the corresponding corrective ability and minimum computer resources required (in real-time monitoring) are executed.

To solve the ICI processing (ICIP) problem it is necessary to design the formal mechanism of description the CNE states and structures, the ICI operating means and ICIP algorithms. Let’s consider these means.

3. Specifying the World Model

It is suggested to carry out the CNE structure and state description using attributive grammars language means [2]. The elements of this language are:

GA = <V_t, V_n, S, O, P, A, F>.

V_t is a set of the terminal symbols which denote the primary CNE (Terminal Devices, Commutators, Channel Equipment etc.).

V_n is a set of the nonterminal symbols, which are put into the correspondence with the derivative CNE (formed on the base of the organizational-technical construction of the CNE from the primary ones, e.g. Communicati on Lines, Communication Lines Sections).

S is a set of the initial symbols (a subset of V) denoting the CN top level derivative elements (e.g. the CN themselves).

O = { &, U , *, # } is a set of the combination operations (on the basis of using such CNE relation types as "a part" - "a whole", "a resource" - "a consumer" although taking into account the parallel and consequent inclusion types of the object "a part" into the obj ect - "a whole"): conjunction (&) is a consequent CNE connection; disjunction (U ) is a parallel CNE connection; excluding OR (*) is a possibility of CNE realization by choosing one from several proper elements; multiform (# ) is a combination of the alternative variants of the CNE structure representation (e.g. the structure of the communication line section is denoted by this operation with the conjunction of the communication line intervals and disjunction of the communic ation line pairs as arguments).

P is a set of the reasoning rules corresponding to the CNE transition operations from one to another by their descriptive symbols substitution or concatenation on the basis of operation application.

A - a set of attributes: input (A_in), synthesized (A_s), inherited (A_i) and output (A_out)); F - a set of mappings which put the attributes from A

into correspondence with the symbols from V. Symbol denoting attributes can reflect: the state (e.g. norm (N), crash (C), warning(W)), probability characteristics, certainty factors, assurance measures, the CNE state possib ility values [2].

4. Mechanisms for Reasoning with Uncertainty

In this paper among the investigated methods adequate to the solving problem (fig.1) we shall distinguish the multivalued logic methods and certainty factors methods [1].

For using multivalued logics information incompletence and contradiction require the state alphabet enlargement. So in accordance with the finite approximation theory to describe the low level CNE state we used the logic A4 with four truth values and for the top level CNE - the logic A8 with eight truth values (fig.2). The certainty factors mechanism employs the model where the units are the belief and disbelief measures of the CNE status hypothesis. For every used CNE c ombining way (defined by the combination operations) we have represented the attribute value synthesis and inheritance rules.

5. Algorithms for Uncertainty Processing

ICIP algorithms can be distinguished by (1) the theoretical mechanisms they are employ, (2) the structure and complexity, (3) the degree of using knowledge about the CNE structural-logical relations, (4) the application of the CNE additional information, etc. In the simplest case the algorithm performance can be based only on the majority processing of the input information. More sophisticated algorithms use the knowledge about the CNE structure and other networks characteristics. The realization of the combined algorithms which provide initially the majority processing and then the execution of more sophisticated algorithms is possible.

Suggested logical means allow to construct the following ICIP class of algorithms, which main essence reduces to iterative synthesis and inheritance of attributes for real-time processing. Let us take that the values to the input attri butes are assumed from the CNE state messages. The synthesized attributes of the symbols in V_n are evaluated through the attributes of these symbol descendants, and the synthesized attributes of the symbols in V_t are a ssumed the input attribute values of these symbols. The inherited attributes of all symbols, except symbols from S, are defined on the base of the attribute values of these symbol ancestors. The inherited attributes of the symbols in S are assumed these symbol input attribute values. The output attributes receive the values as a result of the algorithm execution.

After the values of input (A), synthesized (B) and inherited (C) attributes were determined the iterative evaluation of the output attributes (D) is performed. The one iteration performance consists of the t wo stages. First, the values of the unknown attributes D are determined as a result of the A, B, C attribute value comparison rules application (for example, if all A, B, C attributes are equal T, t hen D is equal T). This rules are dependent on the iteration number.

Second, if the some attribute D values were determined as a result of a former stage and undefined output attributes have retained, the consistent synthesis and inheritance based on the known D values is performed. If all output attributes are defined the algorithm execution is stopped.

Otherwise the undefined output attributes are assumed values according to the result of the operation # performance on the attribute A, B, C values. During the next step the compatible values from the basic set are substituted instead of the former values (for example state B is compatible with T, G - with P and F) and the checking of the attribute D synthesis and inheritance operations is carried out. If the substitution of more than one value from the basic set is possible, the value D is not additionally determined and the denoted b y these symbols CNE state have to be defined more precisely.

The certainty factors ICIP algorithm has the same structure as the algorithm considered above. As the calculated attribute values the certainty factors are used.

6. Algorithms Compared and their Quality Indexes

To compare different algorithms developed and to reveal their corrective properties we shall introduce the following quality indexes (comparison criteria) of the ICIP algorithms (tab.1): (1) reliability (the measure of the C NE state conclusion correctness), (2) completeness which characterizes the part of the CNE with their state defined, (3) computational complexity, etc.

Tab.1. CND algorithm basic quality indexes

?

Index Name

Evaluation Formula

1

ICIP Reliability

Pc=Mc/M, Pw=Mw/M

2

Completeness of CNE state determination

Pu=Mu/M

3

Reliability of indicating the communication violation sources
Pc*=Mc*/M*,

P'c*=Mc*/M'*,

P'w*=Mw*/M'*

4

Completeness of indicating the violation sources

Pu*=Mu*/M*

Mc , Mw , Mu - quantity of CNE which state was defined correctly, was defined wrong and requires more precise definition; M - total quantity of determined communication network fragment CNE (M= Mc + Mw + M u); Mc*, Mu* - quantity of defined (calculated) and undefined CNE - violation sources; M* - total quantity of CNE - violation sources (M*= Mc* + Mu*); Mw* - quantity of CNE which were defined wrong as violation sources; M'* - total quantity of CNE which were indicated as violation sources (M'*= Mc* + Mw*).

7. Results of Algorithm Comparison

To evaluate the suggested indexes the ICIP algorithms testing program tools were designed. Algorithms testing was carried out on the CN various structure and complexity models with the following characteristic value ranges: the dis tinguished CNE number - 40-900, the hosts number - 2-40, the switching centers number - 2-20, the capacity of data transmit channels bunch - 1-24. According to the testing results the diagrams dependencies of the indexes Pc, Pw and Pu from the (Mw/M)_in value (equal to the attitude of the CNE with the distorted state at the ICIP algorithm input to the total CNE number) was built (fig.3). In correspondence with the performed evaluations when CN real exploitation ( Mw/M)_in can achieve the value of 0,12-0,28. The suggested ICIP algorithms possesses the sufficient corrective ability to these distortions handling.

8. Conclusion

The formal models developed in our work can serve as a basis for intelligent components of decision support systems. The algorithms investigated provide the significant improvement of reliability and completeness indexes of CNE sta te data. Besides tools described in the paper we have developed real time algorithms for determining from data and knowledge bases the CNE fragment affected by state changes, incompleteness and contradiction degree evaluation rules, adequate ICIP algorit hm selection scheme, violation source determination tools, etc.

References

1. Kotenko I.V. Reasoning Methods in Expert Systems. St.-Petersburg. MTA. 1992 (in Russian).

2. Kotenko I.V. Diagnostics of Telecommunication Networks, MTA, St.-Petersburg, 1992 (in Russian).

Site of Information Technologies
Designed by inftech@webservis.ru.

?	Index Name	Evaluation Formula
1	ICIP Reliability	Pc=Mc/M, Pw=Mw/M
2	Completeness of CNE state determination	Pu=Mu/M
3	Reliability of indicating the communication violation sources	Pc=Mc/M, P'c=Mc/M', P'w=Mw/M'*
4	Completeness of indicating the violation sources	Pu=Mu/M*
Mc , Mw , Mu - quantity of CNE which state was defined correctly, was defined wrong and requires more precise definition; M - total quantity of determined communication network fragment CNE (M= Mc + Mw + M u); Mc, Mu - quantity of defined (calculated) and undefined CNE - violation sources; M* - total quantity of CNE - violation sources (M= Mc + Mu); Mw - quantity of CNE which were defined wrong as violation sources; M'* - total quantity of CNE which were indicated as violation sources (M'= Mc + Mw*).